package DynamicProgramming;

public class p343 {
    class Solution {
        public int integerBreak(int n) {//dp[i] 表示拆分i得到的最大乘积
            int[] dp = new int[n + 1];
            dp[1] = 1;
            dp[2] = 1;
            for(int i = 3; i <= n; i++){
                for(int j = 1; j <= i - j; j++){//3类不同的计算方法进行竞争
                    dp[i] = Math.max(dp[i],Math.max(j * (i - j), j * dp[i - j]));
                }
            }
            return dp[n];
        }
    }
}
